By way of introduction, an approach to digital security that is commonly used is for a certificate authority (CA) which is trusted and empowered to create and sign certificates, to issue a certificate to a certificate holder. The holder can then provide the certificate to a third party as an attestation by the CA that: the holder who is named in the certificate is in fact the person, entity, machine, email address user, etc., that is set forth in the certificate; and typically that a public key in the certificate is, in fact, the holder's public key.
People, devices, processes or other entities dealing with the certificate holder can rely upon the certificate in accordance with the CA's certification practice statement.
A certificate is typically created by the CA digitally signing, with its own private key, identifying information submitted to the CA along with the public key of the holder who seeks the certificate. A certificate usually has an expiration time and/or date, and can be revoked earlier in the event of compromise of the corresponding private key of the certificate holder, or other revocable event.
A public-key infrastructure (PKI), for example, but not limited to, Secure Sockets Layer (SSL) or Transport Layer Security (TLS) (RFC 2246), uses a hierarchical certificate authority structure having a root level, one or more intermediate levels below the root level and a leaf level at the bottom of the hierarchy. The root level preferably includes a root CA. The intermediate levels preferably include one or more intermediate CAs.
Another example of a PKI is described in “RFC 3280-Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile”.
Each client, for example, but not limited to, a web browser, is typically configured with a number of root CA certificates. When establishing a connection with a new entity, such as another web server, the new entity typically provides a chain of certificates going back to the root CA which issued the first certificate in the certificate chain.
Each certificate typically contains the following: a public key; an identity of the certifying secure entity; and optionally policies associated with the secure entity. Each certificate is preferably signed by a private key corresponding to a public key in the next (parent) certificate until reaching the root.
The client generally validates each signature along the chain to come to the conclusion that, indirectly, the root CA is certifying the identity and policies associated with the new entity (for example, that its name is John Doe, that it is valid, that it is entitled to enter a given door, or that it is a web site with a domain name such as www.yet-another-online-store.com, etc.)
As described above, each certificate typically has an expiry date, and is generally treated as valid only till the expiry date, provided that it is not revoked beforehand. Certificates in the leaf level are generally issued with expiry dates, and typically short lifetimes, for several reasons. First, the probability of certificates needing to be revoked is reduced, thereby preventing certificate revocation lists growing unbounded over time. Second, certificates with expiry dates have a business motivation. For example, entities must renew their certificates with the certificate authority intermittently, and pay for it. Third, certificates with expiry dates enable the signing CA to occasionally change the policies of the certificates.
Therefore, certificate expiration, and typically certificates with a short lifetime, is desired in a certificate system. Certificate renewal typically involves generation and transmission of the certificates requiring processing and bandwidth, respectively. In a system with a large number of leaf entities the process of certificate renewal generally requires a large processing overhead and bandwidth.
The following references are also believed to represent the state of the art:
US Published Patent Application 2004/0148505 of Qui;    “PKI: Coming to an Enterprise Near You?” by Andrew Conry-Murray, Network Magazine, August 2002;    “Distributed Storage and Revocation in Digital Certificate Databases” by Javier Lopez, Antonio Mana, Juan J. Ortega and Jose M. Troya, Database and expert systems applications, 11th International Conference, DEXA 2000, proceedings (Lecture Notes in Computer Science Vol. 1873), published by Springer-Verlag, Berlin, Germany; and    “A novel approach to certificate revocation management” by Ravi Mukkamala and Sushil Jajodia, Database and Application Security XV. IFIP TC11/WG11.3 Fifteenth Annual Working Conference on Database and Application Security 2002, published by Kluwer Academic Publishers, Norwell, Mass., USA.
The disclosures of all references mentioned above and throughout the present specification, as well as the disclosures of all references mentioned in those references, are hereby incorporated herein by reference.